package main

import (
	"fmt"
	"local/algorithm/util"
)

/**
Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.

push(x) -- Push element x onto stack.
pop() -- Removes the element on top of the stack.
top() -- Get the top element.
getMin() -- Retrieve the minimum element in the stack.
Example:
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin();   --> Returns -3.
minStack.pop();
minStack.top();      --> Returns 0.
minStack.getMin();   --> Returns -2.

借助辅助栈 空间换时间
![20180814153425646074359.png](http://cdn.bsummer.cn/20180814153425646074359.png)
*/

type MinStack struct {
	data    []int
	mindata []int
}

func Constructor() *MinStack {
	return &MinStack{data: []int{}, mindata: []int{}}
}

func (s *MinStack) Push(e int) {
	if len(s.mindata) == 0 {
		s.mindata = append(s.mindata, e)
	} else {
		m := util.Min(s.mindata[len(s.mindata)-1], e)
		s.mindata = append(s.mindata, m)
	}
	s.data = append(s.data, e)
}

func (s *MinStack) Pop() int {
	e := s.data[len(s.data)-1]
	s.data = s.data[:len(s.data)-1]
	s.mindata = s.mindata[:len(s.mindata)-1]

	return e
}

func (s *MinStack) GetMin() int {
	return s.mindata[len(s.mindata)-1]
}

func (s *MinStack) Top() int {
	return s.data[len(s.mindata)-1]
}

func main() {
	c := Constructor()
	c.Push(-1)
	c.Push(-2)
	fmt.Println(c.GetMin())
}
